//
//  TestOno2OneController.m
//  ProjectDemo
//
//  Created by IOS3 on 2019/1/8.
//  Copyright © 2019 IOS3. All rights reserved.
//

//
// http://sindrilin.com/2018/01/21/key_value.html
// 作者主要讲 hash->Dictionary实现,



#import "TestOno2OneController.h"

@interface TestOno2OneController ()

@end

@implementation TestOno2OneController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    self.view.backgroundColor = UIColor.grayColor;
    
    [self bucketsSort];
}




/// 桶排序
- (void)bucketsSort {
    NSArray<NSNumber *> *numbers = @[@(10), @(8), @(3), @(9), @(3), @(1), @(4), @(6), @(7), @(5)];
    NSUInteger bucketCount = 0;
    
    for (NSNumber *num in numbers) {
        if (bucketCount < num.unsignedIntegerValue + 1) {
            bucketCount = num.unsignedIntegerValue + 1;
        }
    }
    DPrint(@"bucketCount: %lud", (unsigned long)bucketCount);
    
    NSMutableArray<NSNumber *> *buckets = @[].mutableCopy;
    for (NSUInteger idx = 0; idx < bucketCount; idx++) {
        [buckets addObject:@0];
    }
    
    DPrint(@"buckets: %@", buckets);
    // create a bucket(array), count=(numbers.maxValue+1);all value=0;
    
    for (NSNumber *num in numbers) {
        NSUInteger count = buckets[num.unsignedIntegerValue].unsignedIntegerValue;
        buckets[num.unsignedIntegerValue] = @(count + 1);
    }
    DPrint(@"buckets: %@", buckets);
    // bucket[(nums.eachValue)]+=1, -> if(count(idx in nums)) bucket[idx]=count, none=0
    // 此时, array的值为number在numbers中的个数, 有序的index为number的值
    
    NSMutableArray<NSNumber *> *sorted = @[].mutableCopy;
    for (NSUInteger idx = 0; idx < buckets.count; idx++) {
        NSUInteger count = buckets[idx].unsignedIntegerValue;
        while (count--) {
            [sorted addObject:@(idx)];
        }
    }
    DPrint(@"sorted: %@", sorted);
    // 遍历桶, 取value个index, 得到sorted
    // 缺陷, 需要创建桶的个数, 是numbers中的最大值, 即使排序[1, 1000]这么两个元素的数组, 也需要创建1001个桶, 所需空间不可控
}



// value/10
- (NSUInteger)toSmall:(NSNumber *)number {
    return number.unsignedIntegerValue / 10;
}
/// 哈希排序
- (void)hashSort {
    // 将 number中较大值映射成较小值, 减少桶的个数
    
    NSArray<NSNumber *> *numbers = @[@(101), @(89), @(32), @(95), @(33), @(11), @(44), @(62), @(71), @(99)];
    NSUInteger bucketCount = 0;
    for (NSNumber *number in numbers) {
        if (bucketCount < [self toSmall:number] + 1) {
            bucketCount = [self toSmall:number] + 1;
        }
    }
    
    NSMutableArray<NSMutableArray<NSNumber *> *> *buckets = @[].mutableCopy;
    for (NSUInteger idx = 0; idx < bucketCount; idx++) {
        [buckets addObject:@[].mutableCopy];
    }
    for (NSNumber *number in numbers) {
        NSMutableArray *bucket = buckets[number.unsignedIntegerValue / 10];
        [bucket addObject:number];
    }
    
    NSMutableArray<NSNumber *> *sorted = @[].mutableCopy;
    for (NSUInteger idx = 0; idx < buckets.count; idx++) {
        NSMutableArray *bucket = buckets[idx];
        NSArray *sortedBucket = [bucket sortedArrayUsingSelector:@selector(compare:)];
        [sorted addObjectsFromArray:sortedBucket];
    }
    // 这一步用系统排序略去桶中数据排序
    // 因为每个同种数据都是一个数据段数据, 即使继续使用桶排序, 可采用继续缩小范围, 最后取余的方式减小空间
}



// Core Foundation 中, __CFDictionary 定义
/*
 struct __CFDictionary {
     CFRuntimeBase _base;
     CFIndex _count;
     CFIndex _capacity;
     CFIndex _bucketsNum;
     uintptr_t _marker;
     void *_context;
     CFIndex _deletes;
     CFOptionFlags _xflags;
     const void **_keys;
     const void **_values;
 };      */
// 可以看出其内部使用两个指针数组保存 keys/values, 即,其采用了连续存储的方式存储键值对

// hash化是一个取得变量特征的过程，这个过程可以是取出变量的特征，也可以是一个计算

@end
